package com.xieyong.leetcode;

import java.util.Arrays;

public class Leetcode1498 {
    public static void main(String[] args) {
        Leetcode1498 leetcode1498 = new Leetcode1498();
        int[] nums = {3,3,6,8};
        int target = 10;
        int i = leetcode1498.numSubseq(nums, target);
        System.out.println(i);

    }
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int mod = (int) 1e9 + 7;
        int[] pow = new int[n];
        pow[0] = 1;
        for(int i = 1; i < n; i++) pow[i] = (pow[i-1] * 2) % mod;
        Arrays.sort(nums);
        int left = 0, right = n-1, res = 0;
        while(left <= right){
            if(nums[left] + nums[right] > target) right--;
            else{
                res += pow[right - left];
                res %= mod;
                left++;
            }
        }
        return res;
    }
}
